package leetcode.offer_two_special.linked;

import java.util.Stack;

/**
 * @author mazouri
 * @create 2021-09-07 19:26
 */
public class _27_isPalindrome {
    public boolean isPalindrome1(ListNode head) {
        if (head == null) return false;

        Stack<Integer> stack = new Stack<>();
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        slow = slow.next;
        while (slow != null) {
            stack.push(slow.val);
            slow = slow.next;
        }

        while (!stack.isEmpty()) {
            if (stack.pop() != head.val) return false;

            head = head.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;

        //先分割链表  先通过快慢指针找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        //分割，否则成环
        slow.next = null;
        //反转slow后面的节点 pre 头结点
        ListNode head2 = reverse(mid);

        while (head != null && head2 != null) {
            if (head.val != head2.val) return false;

            head = head.next;
            head2 = head2.next;
        }

        return true;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode next = null;

        while (head != null) {
            //在head改变next时保存一下
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}
